package william.dp;

/**
 * @author ZhangShenao
 * @date 2024/4/11
 * @description <a href="https://leetcode.cn/problems/integer-break/description/">...</a>
 */
public class Leetcode343_整数拆分 {
    /**
     * 采用动态规划算法
     * 状态转移公式:integerBreak(n) = Max{1 x integerBreak(n-1), 2 x integerBreak(n-2),...,n-1 x integerBreak(1)}
     * <p>
     * 时间复杂度O(N^N)
     * 空间复杂度O(N) 额外申请了一个状态转移数组 长度为N
     */
    public int integerBreak(int n) {
        //边界条件校验
        if (n <= 1) {
            return 1;
        }

        //创建长度为n+1的状态转移数组state,state[i]表示拆分整数i的乘积最大值
        //初始状态state[1]=1
        int[] state = new int[n + 1];
        state[1] = 1;

        //进行状态转移
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i - 1; j++) {
                //状态转移公式:state[i] = max{j*(i-j),j*state[i-j]}
                int max = Math.max(j * (i - j), j * state[i - j]);
                state[i] = Math.max(max, state[i]);
            }
        }

        //返回结果state[n]
        return state[n];
    }
}
